

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Vector;

public class Board
{

	private BoardElement[][] elements;
	private int[][] distances;

    //Current position of the player on the present board, denoted by
    //x = row, y = column
	private Position playerPosition;
	private List<Position> boxes;
	private List<Goal> emptyGoals;
	private List<Goal> filledGoals;
    private List<Goal> allGoals;
    
    // Captures all Positions that are in a tunnel
    private Tunnel tunnelInformationHolder; 
    
    private Deadlock deadlock;

	public Board()
	{
		playerPosition = null;
		boxes = new ArrayList<Position>();
		emptyGoals = new ArrayList<Goal>();
		filledGoals = new ArrayList<Goal>();
        allGoals = new ArrayList<Goal>();
        checkGoalsForBlocker();
        computeTunnels();
        deadlock = new Deadlock(this); // do this after adding the elements to the board!
	}

    /**
    * Creates a new board that is a copy of the one given as a parameter
    */
    public Board(Board b)
    {
    	//TODO call this() instead of rewrite code, but I*m not sure if the chcekGoalsForBlocker should be called in this constructor too
    	boxes = new ArrayList<Position>();
		emptyGoals = new ArrayList<Goal>();
		filledGoals = new ArrayList<Goal>();
        allGoals = new ArrayList<Goal>();
		        
		
		BoardElement[][] oldEl = b.getElements();

        this.elements = new BoardElement[b.getElements().length][b.getElements()[0].length];
		
		for (int x = 0; x < this.elements.length; x++)
		    for (int y = 0;y < this.elements[0].length;y++)
                this.elements[x][y] = oldEl[x][y];

        for(Position box : b.getBoxes())
            this.boxes.add(box.copy());

        for(Goal emp : b.getEmptyGoals())
            this.emptyGoals.add(emp.copy());

        for(Goal fill : b.getFilledGoals())
            this.filledGoals.add(fill.copy());

        for(Goal goal : b.getAllGoals())
            this.allGoals.add(goal.copy());
		this.setPlayerPosition(b.getPlayerPosition().copy());
		this.setDistances(b.getDistances());
		
		this.deadlock = b.deadlock; // do this after adding the elements to the board!
		this.tunnelInformationHolder = b.tunnelInformationHolder;
    }

    /**
     * Creates a new board based off a list of strings that describe the board. 
     * @param lines
     * @param lNumRows
     */
	public Board(ArrayList<String> lines) {
		
		boxes = new ArrayList<Position>();
		emptyGoals = new ArrayList<Goal>();
		filledGoals = new ArrayList<Goal>();
        allGoals = new ArrayList<Goal>();
		elements = new BoardElement[lines.size()][];
		distances = new int[lines.size()][];
	
		for (int i = 0; i < lines.size(); i++) {
			char[]chars = lines.get(i).toCharArray();
			
			elements[i] = new BoardElement[chars.length];
			distances[i] = new int[elements[i].length];
			for (int j = 0; j < chars.length; j++) 
			{
				elements[i][j] = BoardElement.getBoardElementForChar(chars[j]);
				distances[i][j] = 99999;

				BoardElement element = BoardElement.getBoardElementForChar(chars[j]);
				
				if (element == BoardElement.PLAYER) 
				{
					playerPosition = new Position(i, j);
				}
				else if (element == BoardElement.PLAYER_ON_GOAL) 
				{
					playerPosition = new Position(i, j);
					emptyGoals.add(new Goal(i, j, element));
                    allGoals.add(new Goal(i, j, element));
				}
				else if (element == BoardElement.GOAL) 
				{
					emptyGoals.add(new Goal(i, j, element));
                    allGoals.add(new Goal(i, j, element));
				}
				else if (element == BoardElement.BOX)
				{
					boxes.add(new Position(i, j));
				}
				else if (element == BoardElement.BOX_ON_GOAL)
				{
					boxes.add(new Position(i, j));
					filledGoals.add(new Goal(i, j, element));
                    allGoals.add(new Goal(i, j, element));
				}
			}
		}

		checkGoalsForBlocker();
		calculateDistancesForAllEmptyGoals();
		computeTunnels();
		deadlock = new Deadlock(this); // do this after adding the elements to the board!
	}
	
	
	/**
	 * Moves the element at position p1 to the position of p2.
	 * @param p1 starting position
	 * @param p2 ending position 
	 * @return true if the move was successful, false if it was an invalid move. 
	 */
	public boolean move(Position p1, Position p2) 
	{
		BoardElement elementToMove = this.getElement(p1);
		
		if ((elementToMove == BoardElement.PLAYER) || (elementToMove == BoardElement.PLAYER_ON_GOAL))
		{
			return movePlayer(p1, p2);
		}
		else if ((elementToMove == BoardElement.BOX) || (elementToMove == BoardElement.BOX_ON_GOAL))
		{
			return moveBox(p1, p2);
		}
		
		System.err.println("Trying to move object that isn't BOX or PLAYER");
		return false;
	}
	
	/**
	 * Moves a player from position p1 to position p2. Updates the board 
	 * elements and player's position. It is assumed that the user effectively
     * wants to move the player to p2, so whatever is there will be overwritten
     * 
	 * @param p1 starting position.
	 * @param p2 ending position
	 * @return true if the move was successful, false otherwise.
	 */
	public boolean movePlayer(Position p1, Position p2)
	{
		BoardElement oldElement = this.getElement(p1);
		BoardElement newElement = this.getElement(p2);
		
//		System.out.println("Moving player: " + p1 + " to " + p2);

        if(newElement == BoardElement.WALL)
        {
            System.out.println("Trying to move player into a wall");
            return false;
		}

		if (oldElement == BoardElement.PLAYER) 
        {
			if (newElement == BoardElement.GOAL) 
			{
                if(this.getElement(p1) == BoardElement.PLAYER)
    				elements[p1.getX()][p1.getY()] = BoardElement.EMPTY_FLOOR;
				elements[p2.getX()][p2.getY()] = BoardElement.PLAYER_ON_GOAL;
				playerPosition.updatePosition(p2);
			}
			else
			{
                if(this.getElement(p1) == BoardElement.PLAYER)
			    	elements[p1.getX()][p1.getY()] = BoardElement.EMPTY_FLOOR;
				elements[p2.getX()][p2.getY()] = BoardElement.PLAYER;
				playerPosition.updatePosition(p2);
		    }
		}
		else if (oldElement == BoardElement.PLAYER_ON_GOAL)
		{
			if (newElement == BoardElement.GOAL)
			{
                if(this.getElement(p1) == BoardElement.PLAYER_ON_GOAL)
    				elements[p1.getX()][p1.getY()] = BoardElement.GOAL;
				elements[p2.getX()][p2.getY()] = BoardElement.PLAYER_ON_GOAL;
				playerPosition.updatePosition(p2);
			}
			else 
			{
                if(this.getElement(p1) == BoardElement.PLAYER_ON_GOAL)
    				elements[p1.getX()][p1.getY()] = BoardElement.GOAL;
				elements[p2.getX()][p2.getY()] = BoardElement.PLAYER;
				playerPosition.updatePosition(p2);
			}
		}
		else
		{
			if (newElement == BoardElement.GOAL)
			{
				elements[p2.getX()][p2.getY()] = BoardElement.PLAYER_ON_GOAL;
				playerPosition.updatePosition(p2);
			}
			else 
			{
				elements[p2.getX()][p2.getY()] = BoardElement.PLAYER;
				playerPosition.updatePosition(p2);
			}
			return true;
		}
		return true;
	}

	/**
	 * Moves a Box from position p1 to position p2. Updates the board elements
	 * if move was successful. It is assumed that the destination is a valid
     * place to be overwritten with the box. This check must be made before
     * 
	 * @param p1 starting position
	 * @param p2 ending position
	 * @return true if the move was successful, false otherwise.
	 */
	public boolean moveBox(Position p1, Position p2) 
	{
		BoardElement oldElement = this.getElement(p1);
		BoardElement newElement = this.getElement(p2);
		
//		System.out.println("Moving box: " + p1 + " to " + p2);
		
        if(newElement == BoardElement.WALL)
        {
            System.out.println("Trying to push the box into a wall");
            return false;
        }
		if (oldElement == BoardElement.BOX) 
		{
			if ((newElement == BoardElement.GOAL) || (newElement == BoardElement.PLAYER_ON_GOAL)) 
			{
				
				elements[p1.getX()][p1.getY()] = BoardElement.EMPTY_FLOOR;	
				elements[p2.getX()][p2.getY()] = BoardElement.BOX_ON_GOAL;
                this.updateBoxPosition(p1, p2);
                this.occupyGoal(p2);
                this.calculateDistancesForAllEmptyGoals();
			}
			else
			{
				elements[p1.getX()][p1.getY()] = BoardElement.EMPTY_FLOOR;
				elements[p2.getX()][p2.getY()] = BoardElement.BOX;
                this.updateBoxPosition(p1, p2);

			}
		}
		else if (oldElement == BoardElement.BOX_ON_GOAL)
		{
			this.freeGoal(p1);
			if ((newElement == BoardElement.GOAL) || (newElement == BoardElement.PLAYER_ON_GOAL))
			{
				elements[p1.getX()][p1.getY()] = BoardElement.GOAL;
				elements[p2.getX()][p2.getY()] = BoardElement.BOX_ON_GOAL;
                this.updateBoxPosition(p1, p2);
                this.occupyGoal(p2);
			}
			else 
			{
				elements[p1.getX()][p1.getY()] = BoardElement.GOAL;
				elements[p2.getX()][p2.getY()] = BoardElement.BOX;
                this.updateBoxPosition(p1, p2);
			}
			this.calculateDistancesForAllEmptyGoals();
		}
		else
		{
			System.err.println("Call to moveBox when p1 is not a BOX");
			System.exit(0);
			return false; // not moving a Box or Box_On_Goal
		}
		return true;
	}

	/**
	 * Updates the board to reflect the path taken from moving the player and box
	 * to new position.
     * 
	 * @param path
     * @param box Position of the box that is being moved
     * @param goal Position where the box was taken using path
     * @return true if the commit was successful, false otherwise
	 */
	public boolean commitPath(String path, Position box, Position goal) {

//        System.out.println("Committing path: " + path);
//        System.out.println("Player before: " + this.playerPosition);
//          System.out.println("For: " + box + " - " + goal);
//		System.out.println(this);

		// update box's position and board
        if(!moveBox(box, goal))
            return false;

		// update player position to be the opposite of the last move in path from goal position
		Position newPlayerPosition = reverseMove(path.charAt(path.length()-1), goal);
		
        if(!movePlayer(playerPosition, newPlayerPosition))
            return false;
//        if(this.getElements()[3][5].getCharacter() == BoardElement.EMPTY_FLOOR.getCharacter())
//        {
//        	System.out.println("Board changed");
//        	//System.exit(0);
//        }
//        System.out.println(this);
//        System.out.println("Player after: " + this.playerPosition);        
        return true;
	}
	
	/**
	 * Returns the position before the reaching end position. 
	 * @param direction Direction that led to the end position.
	 * @param endP the end position 
	 * @return the resulting position 
	 */
	private Position reverseMove(char direction, Position endP) 
	{
		if (direction == 'U') 
		{
			return new Position(endP.getX()+1, endP.getY()); // down
		}
		if (direction == 'D')
		{
			return new Position(endP.getX()-1, endP.getY()); // up
		}
		if (direction == 'L') 
		{
			return new Position(endP.getX(), endP.getY()+1); // right
		}
		if (direction == 'R')
		{
			return new Position(endP.getX(), endP.getY()-1); // left
		}
		return null;
	}
	
	protected List<Goal> getFilledGoals()
	{
		return filledGoals;
	}

	protected void setFilledGoals(List<Goal> filledGoals)
	{
		this.filledGoals = filledGoals;
	}

	public Position getPositionLeftOf(Position position)
	{
		return new Position(position.getX(), position.getY() - 1);
	}

	public Position getPositionRightOf(Position position)
	{
		return new Position(position.getX(), position.getY() + 1);
	}

	public Position getPositionTopOf(Position position)
	{
		return new Position(position.getX() - 1, position.getY());
	}

	public Position getPositionBottomOf(Position position)
	{
		return new Position(position.getX() + 1, position.getY());
	}
	
	/**
	 * This method overrides the method toString of class Object. 
	 * It prints the board as it is send by the server.
	 */
	@Override
	public String toString()
	{
		String result = "";
		for (int x = 0; x<elements.length;x++)
		{
//			result += x;
			for (int y = 0; y < elements[x].length; y++)
			{
			   result+=elements[x][y].getCharacter();
			}
			result+="\n";
		}
		return result;
	}


	/**
	 * Returns a copy of itself. 
	 * @return Board
	 */
	public Board copyBoard()
	{
		Board newBoard = new Board();
		newBoard.setElements(getElements().clone());
		newBoard.getBoxes().addAll(getBoxes());
		newBoard.getEmptyGoals().addAll(getEmptyGoals());
		newBoard.getFilledGoals().addAll(getFilledGoals());
		newBoard.setPlayerPosition(getPlayerPosition());
		return newBoard;
	}

    /**
    * Checks if the current board is in a final configuration, which is
    * that all boxes are on a goal
    *
    * @return True if the board is a final configuration, false otherwise
    */
    public boolean isFinal()
    {
        for(Position box : this.boxes)
        {
            if(this.elements[box.getX()][box.getY()] != 
               BoardElement.BOX_ON_GOAL)
                return false;
        }
        return true;
    }

	/**
	 * checks the neighbors of all goals. If a goal is surrounded by 4 walls
	 * and/or other goals, this goal is maybe no longer reachable if a box is on
	 * a neighbor goal. This method will add possible blocker goals to the
	 * blockerGoals-List. NOTE: If the list has more than one entry, the goal is
	 * only blocked if ALL goals in the list are filled with a box and NOT if
	 * only ONE goal is filled with a box!
	 * e.g		e.g
	 * # #		#B
	 * #B#		#BB
	 * #B#		###
	 * ###
	 */
	private void checkGoalsForBlocker()
	{
		List<Goal> goals = getAllGoals();
		for (Goal goal : goals)
		{
			int surrounded = 0;
			List<Goal> possibleBlockers = new ArrayList<Goal>();
			if (this.getElement(getPositionBottomOf(goal)).getCharacter()
					== BoardElement.WALL.getCharacter())
			{
				surrounded++;
			}
			if (this.getElement(getPositionTopOf(goal)).getCharacter() 
					== BoardElement.WALL.getCharacter())
			{
				surrounded++;
			}
			if (this.getElement(getPositionLeftOf(goal)).getCharacter()
					== BoardElement.WALL.getCharacter())
			{
				surrounded++;
			}
			if (this.getElement(getPositionRightOf(goal)).getCharacter()
					== BoardElement.WALL.getCharacter())
			{
				surrounded++;
			}
			if ((this.getElement(getPositionBottomOf(goal)).getCharacter()
					== BoardElement.BOX_ON_GOAL.getCharacter())
			     || 
			     (this.getElement(getPositionBottomOf(goal)).getCharacter()
			    		 == BoardElement.BOX.getCharacter()))
			{
				surrounded++;
				possibleBlockers.add(new Goal(getPositionBottomOf(goal)));
			}
			if ((this.getElement(getPositionTopOf(goal)).getCharacter()
					== BoardElement.BOX_ON_GOAL.getCharacter())
				|| 
				(this.getElement(getPositionTopOf(goal)).getCharacter()
						== BoardElement.BOX.getCharacter()))
			{
				surrounded++;
				possibleBlockers.add(new Goal(getPositionBottomOf(goal)));
			}
			if ((this.getElement(getPositionLeftOf(goal)).getCharacter()
					== BoardElement.BOX_ON_GOAL.getCharacter())
					|| (this.getElement(getPositionLeftOf(goal)).getCharacter()
							== BoardElement.BOX.getCharacter()))
			{
				surrounded++;
				possibleBlockers.add(new Goal(getPositionBottomOf(goal)));
			}
			if ((this.getElement(getPositionRightOf(goal)).getCharacter()
					== BoardElement.BOX_ON_GOAL.getCharacter())
					|| 
					(this.getElement(getPositionRightOf(goal)).getCharacter()
							== BoardElement.BOX.getCharacter()))
			{
				surrounded++;
				possibleBlockers.add(new Goal(getPositionBottomOf(goal)));
			}

			if (surrounded == 4)
			{
				goal.addBlockerGoals(possibleBlockers);
			}
			else if (surrounded > 4)
			{
				System.err.println("checkGoalsForBlocker(): surrounded is > 4. This should not happen. Max value is 4.");
			}
		}
	}

   /**
    * Compares two boards for equality. It is assumed that both boards
    * have the same size
    *
    * @param b Board to which this should be compared to
    * @return true if the boards are the same, false otherwise
    */
    public boolean equals(Board b)
    {
        for(int i = 0; i < this.elements.length; ++ i)
        {
            for(int j = 0; j < this.elements[0].length; ++ j)
            {
                Position p = new Position(i, j);
                if(this.getElement(p).getCharacter() != b.getElement(p).getCharacter())
                    return false;
            }
        }
        return true;
    }
	
	public BoardElement[][] getElements()
	{
		return elements;
	}

	public void setElements(BoardElement[][] elements)
	{
		this.elements = elements;
	}

	public void setPlayerPosition(Position playerPosition)
	{
		this.playerPosition = playerPosition;
	}

	public void setBoxes(List<Position> boxes)
	{
		this.boxes = boxes;
	}

	public void setEmptyGoals(List<Goal> goals)
	{
		this.emptyGoals = goals;
	}

    public BoardElement getElement(Position p)
    {
        return elements[p.getX()][p.getY()];
    }
    
    public int getNumRows()
    {
        return elements.length;
    }

    public int getNumCols()
    {
        return elements[0].length;
    }

	public Position getPlayerPosition()
	{
		return playerPosition;
	}

	public List<Position> getBoxes()
	{
		return boxes;
	}

	public List<Goal> getEmptyGoals()
	{
		return emptyGoals;
	}

    public List<Goal> getAllGoals()
    {
        return this.allGoals;
    }

    public int[][] getDistances()
	{
		return distances;
	}

    public void setDistances(int[][] distances)
	{
		this.distances = distances;
	}

   /**
    * Changes the value of the position of the indicated box on the internal
    * array if an invalid box is given, no change will be done to the array
    *
    * @param box Box to be updated
    * @param newPlace New position for the box
    */
    private void updateBoxPosition(Position box, Position newPlace)
    {
        for (Position b : this.boxes)
        {
            if (b.equals(box))
            {
                b.setX(newPlace.getX());
                b.setY(newPlace.getY());
                break;
            }
        }
    }
    
	/*
	 * calculates the distances of each position to the nearest available goal
	 */
	public void calculateDistancesForAllEmptyGoals()
	{
		for (Goal goal : emptyGoals)
		{
			updateDistancesForNew(goal);
		}
	}
    
	/*
	 * Updates the distances of each position for the given goal. should be
	 * called if a goal which was a BOX_ON_GOAL is now a GOAL
	 */
	public void updateDistancesForNew(Position goal)
	{
		int x = goal.getX();
		int y = goal.getY();
		
		for (int i = 0; i < elements.length; i++)
		{			
			for (int j = 0; j < elements[0].length; j++)
			{
				int distance = Math.abs(x - i) + Math.abs(y - j);
				if (distance < distances[i][j])
				{
					distances[i][j] = distance;
				}
			}
		}
	}

	/*
	 * Updates the distances of each position for a goal which is not longer
	 * empty should be called if a goal which was a GOAL is now a BOX_ON_GOAL
	 */
	//TODO something is wrong here... after removing a box the distances are still the same...
	public void updateDistancesForRemoved(Position removedGoal)
	{
//		int x = removedGoal.getX();
//		int y = removedGoal.getY();
//		for (int i = 0; i < elements.length; i++)
//		{
//			for (int j = 0; j < elements[0].length; j++)
//			{
//				int distance = Math.abs(x - i) + Math.abs(y - j);
//				// check whether this goals was responsible for the
//				// distance[i][j] value or not
//				if (distance == distances[i][j]) 
//				{
//					// if yes, reset the distance to a high value and find the
//					// new smallest distance
//					distances[i][j] = 99999;
//					for (Goal goal : emptyGoals)
//					{
//						int newDistance = Math.abs(goal.getX() - i)
//								+ Math.abs(goal.getY() - j);
//						if (newDistance < distances[i][j])
//						{
//							distances[i][j] = newDistance;
//						}
//					}
//				}
//			}
//		}
	}
	
	/*
	* Method on class Board
	* Should indicate if the box indicated is inside a tunnel on the current board
	*
	* @param p Position of the box to be analysed
	* @return True if p is in a tunnel, false otherwise
	*/
	public boolean isInTunnel(Position pos){
		//In a static tunnel
		return false;
//		if (tunnelInformationHolder == null)
//			System.out.println("Null");
//		if (!this.tunnelInformationHolder.getInTunnels().isEmpty() && this.tunnelInformationHolder.getInTunnels().contains(pos))
//			return true;
//		else return false;
	}
	//computes all static Tunnels 
	public void computeTunnels()
	{
		long time = System.currentTimeMillis();
		this.tunnelInformationHolder = new Tunnel();
		Vector<Position> p = null;
		boolean closedInTheBeginning = false; //For remember if the tunnel was closed in the beginning (blind alley) --> No tunnel
		for (int i = 0; i < this.elements.length-2; i++)
		{
			int first = i;
			int second = i+2;
			// check rows for tunnels
			
			for (int j = 0; j < Math.min(this.elements[first].length, this.elements[second].length); j++)
			{
				if (this.elements[first][j].getCharacter() == BoardElement.WALL.getCharacter()
						&& this.elements[first+1][j].getCharacter() != BoardElement.WALL.getCharacter() 
						&& this.elements[first][j].getCharacter() == this.elements[second][j].getCharacter())
				{
					//in a tunnellike piece check if both ends are open 
					if (p==null && !closedInTheBeginning && j-1 >= 0 && this.elements[first+1][j-1].getCharacter() != BoardElement.WALL.getCharacter() )
					{
						p = new Vector<Position>();
						p.add(new Position(i+1,j));
					}
					else if (j-1 <  0 || this.elements[first+1][j-1].getCharacter() == BoardElement.WALL.getCharacter() )
					{
						//Tunnel is closed in the beginning
						closedInTheBeginning = true; 
					}
					else if (p!=null)
						p.add(new Position(i+1,j));
						
				}
				else if (p!= null && this.elements[first+1][j].getCharacter() != BoardElement.WALL.getCharacter())
				{
					this.tunnelInformationHolder.addTunnelPosition(p);
					closedInTheBeginning = false;
					p = null;
				}
				else if (p!= null && this.elements[first+1][j].getCharacter() == BoardElement.WALL.getCharacter())
				{
					//Tunnel is closed at the end --> Blind alley
					closedInTheBeginning = false;
					p = null;
				}
			}
		}
		//longest line
		closedInTheBeginning = false; //For remember if the tunnel was closed in the beginning (blind alley) --> No tunnel
		int maxLine = 0;
		p = null;
		for ( int i = 0; i < this.elements.length; i++)
		{
			if (this.elements[i].length > this.elements[maxLine].length)
			{
				maxLine = i;
			}
		}
		
		// check columns for tunnels
		for (int i = 0; i < this.elements[maxLine].length; i++)
		{
			
			
			for (int j = 0; j < this.elements.length; j++)
			{
				if (i < this.elements[j].length-2 )//&& i < this.elements[j+2].length-2)
				{
					if (this.elements[j][i].getCharacter() == BoardElement.WALL.getCharacter()
							&& this.elements[j][i+1].getCharacter() != BoardElement.WALL.getCharacter() 
							&& this.elements[j][i+2].getCharacter() == this.elements[j][i].getCharacter())
					{
						//in a tunnellike piece check if both ends are open 
						if (p==null && !closedInTheBeginning && j-1 >= 0 && this.elements[j-1][i+1].getCharacter() != BoardElement.WALL.getCharacter() )
						{
							p = new Vector<Position>();
							p.add(new Position(j,i+1));
						}
						else if (i-1 <  0 || this.elements[j-1][i+1].getCharacter() == BoardElement.WALL.getCharacter() )
						{
							//Tunnel is closed in the beginning
							closedInTheBeginning = true; 
						}
						else if (p!=null)
							p.add(new Position(j,i+1));
						
					}
					
					else if (p!= null && this.elements[j][i+1].getCharacter() != BoardElement.WALL.getCharacter())
					{
						this.tunnelInformationHolder.addTunnelPosition(p);
						closedInTheBeginning = false;
						p = null;
					}
					else if (p!= null && this.elements[j][i+1].getCharacter() == BoardElement.WALL.getCharacter())
					{
						//Tunnel is closed at the end --> Blind alley
						closedInTheBeginning = false;
						p = null;
					}
				}
				
			}
		}
		
		
		//TODO Just for testing, remove after testing
		if(Client.debug)
		{
			Vector<Position> res = this.tunnelInformationHolder.getInTunnels();
			for (int i = 0; i < res.size(); i++)
			{
				System.out.println(res.get(i));
			}
		}
		
//		
//		System.out.println("Time For Static Tunnels: "+(System.currentTimeMillis()-time)+" ms");
		
	}

	public Deadlock getDeadlock() {
		return this.deadlock;
	}
	
	/*
	* Method on class Board
	* Moves the box indicated to the first position outside of the tunnel, or to the first goal that comes upon the way
	* It is assumed that the indicated box is inside a tunnel (checked by isInTunnel)
	*
	* @param box Position of the box to be pushed outside of the tunnel
	* @param dir Indicates the direction in which the box should be pushed (true = right|bottom, false = left|top)
	* @return The steps taken to perform the push, or null if this is not possible (box at the exit
	*/
	public String commitTunnel(Position box, boolean dir)
	{
	    if (!this.isInTunnel(box)) return null;
	    int xChange = 0;
	    int yChange = 0;
	    String put = "";
	    String path = "";
	    
	    if(dir == true)
	    {
	        if (this.getElement(getPositionRightOf(box)).getCharacter()
	        		== BoardElement.WALL.getCharacter())
	        {
	        	path = Client.findPath(this.playerPosition, this.getPositionTopOf(box), this);
	        	if(path == null)
	        		return null;
	            put = "D";
	            xChange = 1;
	        }
	        else
	        {
	        	path = Client.findPath(this.playerPosition, this.getPositionLeftOf(box), this);
	        	if(path == null)
	        		return null;
	            put = "R";
	            yChange = 1;
	        }
	    }
	    else
	    {
	        if (this.getElement(getPositionLeftOf(box)).getCharacter() 
	        		== BoardElement.WALL.getCharacter())
	        {
	        	path = Client.findPath(this.playerPosition, this.getPositionBottomOf(box), this);
	        	if(path == null)
	        		return null;
	            put = "U";
	            xChange = -1;
	        }
	        else
	        {
	        	path = Client.findPath(this.playerPosition, this.getPositionRightOf(box), this);
	        	if(path == null)
	        		return null;
	            put = "L";
                yChange = -1;
	        }
	    }
	    Position pos = box.copy();
	    if (this.getElement(pos)==BoardElement.BOX_ON_GOAL)
        {
        	return null;
        }
	    while(this.isInTunnel(pos))
	    {
	        pos = new Position(pos.getX() + xChange, pos.getY() + yChange);
	        if (this.getElement(pos).getCharacter() != BoardElement.BOX.getCharacter() &&
	                this.getElement(pos).getCharacter() != BoardElement.BOX_ON_GOAL.getCharacter())
	        {
	            path+=put;
	            if (this.getElement(pos)==BoardElement.GOAL)
	            {
	                this.commitPath(path, box, pos);
	                return path;
	            }
	            
	        }
	        else return null;
	    }
	    
	    this.commitPath(path, box, pos);
	    return path;
	    
	}
	
	private void occupyGoal(Position g)
	{
		for(int i = 0; i < this.emptyGoals.size(); ++ i)
		{
			Goal free = emptyGoals.get(i); 
			if(free.equals(g))
			{
				this.emptyGoals.remove(i);
				this.filledGoals.add(free);
				break;
			}
		}
	}
	
	private void freeGoal(Position g) 
	{
		for(int i = 0; i < this.filledGoals.size(); ++ i)
		{
			Goal fill = this.filledGoals.get(i);
			if(fill.equals(g))
			{
				this.filledGoals.remove(i);
				this.emptyGoals.add(fill);
				break;
			}
		}
	}
	
	public String getKey()
	{
		
		Position moveableArea = Client.findUpperLeftCorner(getPlayerPosition(), this);
		List<Position> sortedBoxes = new ArrayList<Position>();
		sortedBoxes.addAll(this.getBoxes());
		BoxComparator comp = new BoxComparator();
		Collections.sort(sortedBoxes, comp);		
		
		String hash = "";
		hash += moveableArea.getX() + "," + moveableArea.getY() + ";";
		
		for (Position box : sortedBoxes)
		{
			hash+= box.getX() + "," + box.getY() + ";";
		}			
		
		return hash;
	}
}
